"""
给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

递归遍历
因为不必经过根节点所以要将这种情况考虑进去
就加了一个 res 和 l + r + val 的比较
如果左右子树的值是小于零的也就是说对结果没有好处就重置为零
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root: return 0
        self.res = root.val
        def maxSum(r):
            if not r: return 0
            left = max(0,maxSum(r.left))
            right = max(0,maxSum(r.right))
            self.res = max(self.res, left+right+r.val)
            return max(left,right)+r.val
        maxSum(root)
        return self.res